package com.breeze.leetcode;

/**
 * https://leetcode-cn.com/problems/reverse-linked-list/
 * 206:反转链表
 */
public class LeetCode206 {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 迭代法
     */
    public ListNode reverseList(ListNode head) {
        /*ListNode res = null;
        while (head != null) {
            // 该种方法虽然可以实现，但是不实用，如果ListNode参数较多，需要进行拷贝
            ListNode node = new ListNode(head.val);
            node.next = res;
            res = node;
            head = head.next;
        }
        return res;*/

        // 遍历结点时，prev始终为当前元素的上个结点链表
        ListNode prev = null;
        // 表示当前结点
        ListNode curr = head;
        while (curr != null) {
            // curr需要卸掉头结点，故需要通过next保存剩余的链表
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    /**
     * 递归法
     */
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = reverseList1(head.next);
        head.next.next = head; // head.next 是已反转链表的链尾，然后让链尾指向当前结点
        head.next = null; // 需要记得断开当前结点的next
        return p;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        LeetCode206 leetCode206 = new LeetCode206();
        ListNode res = leetCode206.reverseList(head);

        while (res != null) {
            System.out.print(res.val + "->");
            res = res.next;
        }
    }
}
